1. Technical Field
This invention relates in general to data processing methods and devices and more specifically in its illustrated embodiment to a method and apparatus for database management of records.
2. Background Art
Database management or transaction processing systems are well known in the prior art. These systems are generally utilized to provide rapid access to database tables which contain a plurality of data records. A relational transaction processing system provides access to multiple database tables where elements of one database table are generally related to elements in another database table. A relational database allows a user to search, access, and alter data contained in multiple database tables using one or more specific elements or fields.
One important aspect of all such database systems is the ability of the system to provide rapid and efficient access to individual records in each database. Recently, database management systems have been provided which support the utilization of the database by multiple users simultaneously, allowing users to access specific data concurrently.
An index file is commonly used by database management programs to provide quick and efficient access to records in tables. These index files are commonly configured in a B-Tree structure. A reference that discusses the B-Tree is "Efficient Locking For Concurrent Operation on B-Tree" by Lehman and Yao, ACM Transactions on Database Systems, volume 6, number 4, December, 1981, pages 650-670. Other references addressing B-Tree structures include "The Ubiquitous B-Tree" by Comer, Computing Surveys, volume 11, number 2, June, 1979, pages 121-137; and "Concurrent Operation on B-Trees with Over Taking" by Sagiv, Proceedings ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, March, 1985, pages 28-37.
The index file configured as a B-Tree structure consists of a root node with many levels of nodes branching from the root node. The information contained in these nodes include pointers to the nodes at the next level or pointers to records in the database. These pointers include further information termed key record information which may reference the records in the database. The record keys are in an ordered form throughout the nodes. For example, an index tree may exist for an alphabetic listing of employee names. The root node would include reference keyed data that relates to records indirectly or directly referenced by the next level of nodes. The reference keys contain information about the index filed, i.e. the alphabetic . spelling of employees name. Therefore, the ordered keys in the root node would point to the next successive level of nodes. In other words, the next successive node may indirectly or directly reference all employees names beginning with A, B, and C. A next successive node, parallel with the first successive node, may contain employee records whose last name begins with the letters D-M. The last successive node on this level would reference records of employees with last names starting with N-Z. As one searches through the index file tree, a bottom node is eventually reached. The contents of the bottom node include record keys that point to the individual records in storage.
One problem in providing concurrent accesses to database tables occurs when multiple transactions are trying to access a record at the same time. Specifically, when one user wishes to change a record and another user is attempting to access this record, a contention situation occurs. One solution to the contention problem is to provide exclusive access (or locking) to the records or to the portions of the B-Tree indexes to ensure that the index node, or record is not changed while the user is attempting to access it. Locking is addressed in "Index Locking and Splitting", IBM Technical Disclosure Bulletin, volume 25, number 7B, December, 1982, pages 3725-3729; and "Locking Protocols for Concurrent Operations on B-Trees", IBM Technical Disclosure Bulletin, volume 19, number 10, March, 1977, pages 3887-3889. The disadvantage of a locking solution is that a lock, while providing access to one user, prevents access by any other user. It should therefore be apparent to those skilled in the art that by minimizing the number of locks utilized it will be possible to enhance the concurrency of a system.
Another important aspect of data processing systems is the capability of such systems to make changes to the data contained within the database in a recoverable manner. That is, these systems ensure that either all of the changes entered by a particular user persists or none of the changes persist in the event the operation of the system is interrupted by failures of various components. Similarly, the user also is given the ability to request that changes the user has made to the database be reversed until a particular point in time has been reached. Thus, the users' changes to the database are said to be "recoverable." This concept is incorporated into database systems which operate in a "transaction" processing manner. A transaction is a logical unit of work comprised of a sequence of operations which transforms a first consistent state of a recoverable database resource into another consistent state without necessarily preserving consistency at all intermediate points in the sequence. The utilization of a transaction processing system will guarantee that if a transaction executes certain updates against a recoverable database resource, and a failure occurs before the transaction reaches its normal termination or an interim point of consistency, then those updates will be undone.
Since a transaction includes the execution of an application-specified sequence of operations, its existence in the system is generally initiated with a special "BEGIN WORK" operation and ends with either a "COMMIT" or an "ABORT". The COMMIT and ABORT operations previously described provide atomicity in the system in that the COMMIT operation signifies that a new point of consistency has been reached and all updates made by the transaction involved must be made permanent. The ABORT operation signifies that a fault has occurred and that any changes made by the particular transaction involved must be "rolled back" or undone, and the recoverable database resources returned to the prior point of consistency.
In order to permit this transaction recovery guarantee, the database system must be able to remember across system outages those transactions which were in progress and the state of their update actions so that the effect of those actions on recoverable data may be properly reflected when the system is restarted. This is accomplished by recording in a log stored on stable storage the progress of each transaction from its beginning to its end, and those actions which cause changes to recoverable data resources. This log then becomes a source for ensuring that the transaction's committed actions are reflected, or that its uncommitted actions are reversed to ensure that the database stays consistent. When the log of transaction operations reflects data object content these log records also become the source for reconstruction of damaged or lost data. These systems generally assign each log record a unique log sequence number (LSN) at the time the record is written into the log. Such LSNs are generally assigned in an ascending numerical sequence. Upon the completion of the logging of an update to a page of memory in the database the LSN of the log record corresponding to the update is also typically stored on that page.
The type of system described above is generally referred to as a log write-ahead system. A log write-ahead system requires that a log entry corresponding to a particular operation must by physically written to stable storage before new versions of the changed data replace the earlier versions of the data on non-volatile storage. Stable storage, as described herein means non-volatile storage which remains intact and available across system failures. One such example is the utilization of a magnetic storage disk. Additionally, such systems store transaction status in the log and no transaction may be considered complete until its committed status and all of its log data is safely recorded on stable storage. Thus, in the event of a system failure, a restart procedure will recover any operations within the transaction which were completed successfully but did not manage to get their updated resources physically written to stable storage prior to the system failure. Further, such systems do not permit a transaction to complete COMMIT processing until all portions of all log records for the transaction have been written to the physical log.